package LeetCode.interview;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
 原题

　　Implement strStr(). 
　　Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. 

题目大意

　　实现实现strStr()函数，判断一个字符串在另一个字符串中出现的位置。如果不匹配就返回-1。 

解题思路
	字符串子串匹配
　　使用朴素字符串匹配算法(或KMP)进行实现 

 * @Date 2017-09-24 23：55
 */
public class _028_Implement_strStr {
    /**
     * 使用朴素字符串匹配算法
     * @param haystack	文本
     * @param needle	子串
     * @return
     */
	public int strStr(String haystack, String needle) {
		if (needle==null || haystack==null)	return -1;
		if (needle.length() > haystack.length())	return -1;
		if (needle.equals(""))				return 0;
	
		if (needle.equals("") && haystack.equals(""))	return 0;
			
		int N = haystack.length();
		int M = needle.length();
		int i, j;
		for (i = 0; i <= N-M; i ++) {
			for (j = 0; j < M; j ++) {
				if (needle.charAt(j) != haystack.charAt(i+j))	
					break;
			}
			if (j == M)	return i;
		}
		return -1;
    }

	public static void main(String[] args) {
		LogUtils.println("结果", new _028_Implement_strStr().strStr("a", ""));
		
	}
}
